What are the two properties of a binary heap?
- Shape Property (must be a Complete Binary Tree)
- Heap Property (e.g., Parent ≥ Children for a Max-Heap)
How do we insert an element?
Add the element to the end of the array to maintain the shape, then bubble it up to restore the heap property.
How do we extract the max element?
Replace the root with the last element, then bubble it down to restore the heap property.
What is the time complexity of `insert` and `extractMax`?
Both operations depend on the height of the tree, resulting in a time complexity of \(O(\log n)\).
What are the two properties of a binary heap?
- Shape Property (Complete Binary Tree)
- Heap Property (Max-Heap or Min-Heap)
How do we insert an element?
Add to end, then bubble up.
How do we extract the max element?
Replace root with last element, then bubble down.
What is the time complexity of `insert` and `extractMax`?
\(O(\log n)\)